package com.yan_jiu_sheng.LeetCodeHot100.AC;

import java.util.*;

/**
 * https://leetcode.cn/problems/top-k-frequent-elements/description/?envType=study-plan-v2&envId=top-100-liked
 * 哈希表+大顶堆  自我AC通过
 *
 * @author yulongTian
 * @create 2024-07-14 18:49
 */
public class Test72 {
    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        int k = 2;
        System.out.println(Arrays.toString(new Test72().topKFrequent(nums, k)));
    }

    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        int[][] basket = new int[map.size()][2];
        int index = 0;
        for (Integer integer : map.keySet()) {
            basket[index][0] = map.get(integer);
            basket[index][1] = integer;
            index++;
        }

        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o2[0] - o1[0];
            }
        });
        priorityQueue.addAll(Arrays.asList(basket));
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = Objects.requireNonNull(priorityQueue.poll())[1];
        }

        return res;
    }

//    /*
////    数组的值范围不是0到100000，不具有一般性
////     */
////    public int[] topKFrequent(int[] nums, int k) {
////        int[][] basket = new int[100001][2];
////        for (int i = 0; i < nums.length; i++) {
////            basket[nums[i]][0]++;
////            basket[nums[i]][1] = nums[i];
////        }
////        Arrays.sort(basket, new Comparator<int[]>() {
////            @Override
////            public int compare(int[] o1, int[] o2) {
////                return o2[0] - o1[0];
////            }
////        });
////        int[] res = new int[k];
////        for (int i = 0; i < k; i++) {
////            res[i] = basket[i][1];
////        }
////        return res;
////    }

}
